package zuo.algo.data;

import zuo.algo.util.SortUtils;

import java.util.Arrays;
import java.util.Random;

public class Heap<E extends Comparable<E>> {

    private Object[] data;
    private int size;

    public Heap() {
        this(16);
    }

    public Heap(int size) {
        this.size = 0;
        this.data = new Object[size];
    }

    public void add(E node) {
        if (size >= data.length) {
            resize();
        }
        data[size++] = node;
        upAdjust(size - 1);
    }

    private void resize() {
        if (size < 0) {
            return;
        }
        Object[] oldData = data;
        data = new Object[oldData.length * 2];
        System.arraycopy(oldData, 0, data, 0, size);
    }

    private void upAdjust(int idx) {
        while (idx > 0) {
            int pIdx = (idx - 1) / 2;
            if (get(idx).compareTo(get(pIdx)) >= 0) {
                break;
            }
            Object temp = data[idx];
            data[idx] = data[pIdx];
            data[pIdx] = temp;
            idx = pIdx;
        }
    }

    public E insert(int idx, E node) {
        if (idx >= size) {
            throw new IllegalStateException("insert idx error");
        }
        E oldNode = get(idx);
        if (node.compareTo(oldNode) == 0) {
            data[idx] = node;
        }
        // 替换值小于当前值，向上调整
        if (node.compareTo(oldNode) < 0) {
            upAdjust(idx);
        }
        // 替换值大于当前值，向下调整
        if (node.compareTo(oldNode) > 0) {
            downAdjust(idx);
        }
        return oldNode;
    }

    public E pop() {
        if (size <= 0) {
            throw new IllegalStateException("no data");
        }
        E node = get(0);
        data[0] = data[--size];
        data[size] = null;
        downAdjust(0);
        return node;
    }

    private void downAdjust(int idx) {
        while (idx < size) {
            int cIdx = idx * 2 + 1;
            if (cIdx >= size) {
                break;
            }
            E cNode = get(cIdx);
            if (cIdx + 1 < size) {
                E node2 = get(cIdx + 1);
                if (node2.compareTo(cNode) < 0) {
                    cIdx += 1;
                    cNode = node2;
                }
            }
            E node = get(idx);
            if (node.compareTo(cNode) <= 0) {
                break;
            }
            data[idx] = cNode;
            data[cIdx] = node;
            idx = cIdx;
        }
    }

    public E get(int idx) {
        if (idx >= size) {
            throw new IllegalStateException("get idx error");
        }
        return (E) data[idx];
    }

    public int size() {
        return this.size;
    }

    public Object[] toArray() {
        return Arrays.copyOf(data, size, data.getClass());
    }

    public static void main(String[] args) {
        Heap<Integer> heap = new Heap<>();
        int[] randomArr = SortUtils.getRandomArr(10, 30);
        for (int num : randomArr) {
            heap.add(num);
        }
        for (int i = 0; i < randomArr.length; i++) {
            System.out.println(heap.pop());
        }
        Random random = new Random();
        int maxLen = 1000;
        int maxVal = 100000;
        for (int i = 0; i < 1000000; i++) {
            int[] arr = SortUtils.getRandomArr(maxLen, maxVal);
            for (int num : arr) {
                heap.add(num);
            }
            for (int j = 0; j < 20; j++) {
                int idx = random.nextInt(arr.length);
                int val = random.nextInt(maxVal);
                heap.insert(idx, val);
            }
            Object[] res2 = heap.toArray();
            int[] res1 = new int[arr.length];
            for (int j = 0; j < arr.length; j++) {
                res1[j] = heap.pop();
            }
            Arrays.sort(res2);
            SortUtils.assertArr(res1, res2);
            System.out.println(i);
        }
    }
}
